package com.base.search.impl.binarysearch;

/**
 * @ClassName FindPeakElement
 * @Description 162. 寻找峰值
 * 峰值元素是指其值严格大于左右相邻值的元素。
 *
 * 给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 *
 * 你可以假设nums[-1] = nums[n] = -∞ 。
 *
 * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-peak-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author li
 * Date 2021/9/15 12:12
 * Copyright
 **/
public class FindPeakElement {
    /**
     * 假如满足条件的结点为X,
     * 那么，如果存在i<X,则nums[i]<nums[i+1]
     *      如果存在i>X,则nums[i]>nums[i+1]
     *
     * 二分查找的思路：
     *
     * 1、首先算出中间结点
     * 2、判断中间结点与左右结点的大小关系：中间小于其中一个，中间大于两边,中间小于两边
     * 3、判断移动方向
     *  3、1 中间小于两边或者中间大于两边，向较大值邻居那个方向移动
     *  3、2 中间小于其中一边，向较大的元素移动
     * 4、返回中间元素
     *
     * @param nums 整数数组
     * @return 峰值序号
     */
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            // 假设X为目标点
            // 表示mid>=X
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            // 表示mid<X,
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
